//
//  Problem337.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 337. 打家劫舍 III
 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

 示例 1:

 输入: [3,2,3,null,3,null,1]

      3
     / \
    2   3
     \   \
      3   1

 输出: 7
 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
 示例 2:

 输入: [3,4,5,1,3,null,1]

      3
     / \
    4   5
   / \   \
  1   3   1

    3
   / \
  4   1001
 / \   \
100 3   1

 输出: 9
 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
 */
@objcMembers class Problem337: NSObject {
    /*
     3
    / \
   4   5
  / \   \
 100 3   1
     */
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(2)
        root.left?.right = TreeNode(3)
        
        root.right = TreeNode(3)
        root.right?.right = TreeNode(1)
        
//        print(rob(root))
        print(robDP(root).max())
    }
    
    /*
     超时
     */
    func rob(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        } else if root?.left == nil, root?.right == nil {
            return root!.val
        }
        
        return max(root!.val + rob(root?.left?.left) + rob(root?.left?.right) + rob(root?.right?.left) + rob(root?.right?.right), rob(root?.left) + rob(root?.right))
    }
    
    /*
     动态规划
     dp[0]:表示:不偷该节点获取的最大利益
     dp[1]:表示:偷该节点获取的最大利益
     
     */
    func robDP(_ root: TreeNode?) -> [Int] {
        guard let node = root else {
            return [0, 0]
        }
        
        
        
        let leftInfo = robDP(root?.left)
        let rightInfo = robDP(root?.right)
        
        // 当前节点有2个选择
        // 1: 偷当前节点, 那么左右节点就不能偷了
        let tou = node.val + leftInfo[0] + rightInfo[0]
        // 2: 不偷当前节点, 那么我看看 左节点偷利益大呢还是不偷利益大呢？
        let butou = max(leftInfo[1], leftInfo[0]) + max(rightInfo[0], rightInfo[1])
        
        return [butou, tou]
    }
}
